package com.clstu.graph;

import java.util.*;

/**
 * 图的研究(左神版,注重的是图的表达!!!)
 */
public class Graph2 {
    public  HashMap<Integer,Node> nodes;//点集(点编号,实际的点)
    public  HashSet<Edge> edges;//边集

    public static void main(String[] args) {
//        int[][] arr = { {0, 1, 1, 0, 0},
//                        {1, 0, 1, 1, 1},
//                        {1, 1, 0, 0, 0},
//                        {0, 1, 0, 0, 0},
//                        {0, 1, 0, 0, 0}};
        int[][] arr = { {0,1,1,0,0,0,0,0},
                        {1,0,0,1,1,0,0,0},
                        {1,0,0,0,0,1,1,0},
                        {0,1,0,0,0,0,0,1},
                        {0,1,0,0,0,0,0,1},
                        {0,0,1,0,0,0,1,0},
                        {0,0,1,0,0,1,0,0},
                        {0,0,0,1,1,0,0,0}};
        Graph2 graph = createGraph(arr);
        System.out.println("=====广度优先=====");
        graph.bfs(graph.nodes.get(0));//宽度优先
        System.out.println("=====深度优先======");
        graph.dfs(graph.nodes.get(0));//深度优先
    }

    //构造器
    public Graph2(){
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }

    //编写方法实现广度优先遍历
    public void bfs(Node node){
        //思路分析,
        //1.队列用于遍历,set用于判断是否已经遍历过
        //2.循环从队列种取节点,输出,同时将它不重复的邻接节点都加入到队列便于后面取出打印,
        //如果不用打印
        if(node == null){
            return;
        }
        //用Set和Queue实现广度遍历
        Queue<Node> nodes = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();
        //头节点入队列和set
        nodes.add(node);
        set.add(node);
        //遍历
        while (true){
            //如果遍历完
            if(nodes.isEmpty()){
                break;
            }
            //取出打印
            Node cur = nodes.poll();
            System.out.println(cur);
            //添加cur的临接节点
            for (Node n : cur.nextList) {
                //如果不重复
                if(!set.contains(n)){
                    nodes.add(n);
                    set.add(n);
                }
            }
        }
    }

    //编写方法实现深度优先遍历
    public void dfs(Node node){
        //思路分析,
        //仍然有队列和集合来判断,
        //1.先将头节点入栈
        //2.先将传入的节点加入栈和集合,并且打印
        //3.循环从队列中取数据,然后加入它的邻接节点,
        // 只要集合中不存在,就先将打印过的先压入(目的是保持广度,深度优先但也要能遍历完整个图),在加入这不存在的节点
        // 成功加入一个就输出一个.就进入下一轮循环,(从队列种取数据)
        //如果不用打印
        if(node == null){
            return;
        }
        //初始化
        Stack<Node> nodes = new Stack<>();
        HashSet<Node> set = new HashSet<>();
        nodes.add(node);
        set.add(node);
        //打印第一个节点
        System.out.println(node);
        while (true){
            //如果遍历完
            if(nodes.isEmpty()){
                break;
            }
            Node cur = nodes.pop();
            for (Node n : cur.nextList) {
                //每次只加入一个,且加入一个打印一个,
                if(!set.contains(n)){
                    //push(cur)的目的是回溯,相当于走到死路后可以回到一步换条路走,避免遍历不完
                    nodes.push(cur);
                    nodes.push(n);
                    set.add(n);
                    //加入成功一个才打印,且打印后马上退出本层循环保证深度优先
                    System.out.println(n);
                    break;
                }
            }
        }
    }

    //编写方法根据临界矩阵创建图
    public static Graph2 createGraph(int[][] arr){
//        new ArrayList<>()
        //创建图
        Graph2 graph2 = new Graph2();
        //添加节点
        for (int i = 0; i < arr.length; i++) {
            graph2.nodes.put(i,new Node("p"+(char)('1'+i)));
        }
        //添加边,调整图
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                //如果有边
                if (arr[i][j] != 0) {
                    //得到边的起点终点权重
                    Node from = graph2.nodes.get(i);
                    Node to = graph2.nodes.get(j);
                    int weight = arr[i][j];
                    //创建边
                    Edge edge = new Edge(from, to, weight);
                    //调整
                    from.nextList.add(to);
                    from.out++;
                    to.in++;
                    from.edges.add(edge);
                    graph2.edges.add(edge);
                }
            }
        }
        return graph2;
    }

    //编写方法实现拓扑排序
//    public static

}

/**
 * 节点类
 */
class Node{
    public String value;//节点数据
    public int in;//入度
    public int out;//出度
    public ArrayList<Node> nextList;//邻接节点
    public ArrayList<Edge> edges;//边

    //构造器
    public Node(String value){
        this.value = value;
        in=0;
        out=0;
        nextList = new ArrayList<>();
        edges = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Node{" +
                "value='" + value + '\'' +
                ", in=" + in +
                ", out=" + out +
                '}';
    }
}
/**
 * 边类
 */
class Edge{
    public int weight;//距离
    public Node from;//起点
    public Node to;//终点

    //构造器
    public Edge(Node from, Node to,int weight) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}